/*
 * @Author: your name
 * @Date: 2021-03-23 11:01:15
 * @LastEditTime: 2021-04-08 16:22:24
 * @LastEditors: lily
 * @Description: In User Settings Edit
 * @FilePath: \js_leetcode\code\14.最长公共前缀.js
 */
/*
 * @lc app=leetcode.cn id=14 lang=javascript
 *
 * [14] 最长公共前缀
 */

// @lc code=start
/**
 * @param {string[]} strs
 * @return {string}
 */

//  思路：
//  当字符串数组长度为 0 时则公共前缀为空，直接返回
//  令最长公共前缀 ans 的值为第一个字符串，进行初始化
//  遍历后面的字符串，依次将其与 ans 进行比较，两两找出公共前缀，最终结果即为最长公共前缀
//  如果查找过程中出现了 ans 为空的情况，则公共前缀不存在直接返回

//  复杂度：O(s)，s 为所有字符串的长度之和  O(1)

var longestCommonPrefix = function (strs) {
    if (strs.length == 0)
        return "";
    let ans = strs[0];
    for (let i = 1; i < strs.length; i++) {
        let j = 0;
        for (; j < ans.length && j < strs[i].length; j++) {
            if (ans[j] != strs[i][j])
                break;
        }
        ans = ans.substr(0, j);
        if (ans === "")
            return ans;
    }
    return ans;


};
// @lc code=end

console.log(longestCommonPrefix(["abab", "aba", ""]));